{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Living People LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAliveYear"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生存人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定 N 个人的出生年份和死亡年份，第 <code>i</code> 个人的出生年份为 <code>birth[i]</code>，死亡年份为 <code>death[i]</code>，实现一个方法以计算生存人数最多的年份。</p>\n",
    "\n",
    "<p>你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。</p>\n",
    "\n",
    "<p>如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\n",
    "birth = [1900, 1901, 1950]\n",
    "death = [1948, 1951, 2000]\n",
    "<strong>输出：</strong> 1901\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt; birth.length == death.length &lt;= 10000</code></li>\n",
    "\t<li><code>birth[i] &lt;= death[i]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [living-people-lcci](https://leetcode.cn/problems/living-people-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [living-people-lcci](https://leetcode.cn/problems/living-people-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1900,1901,1950]\\n[1948,1951,2000]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        dict_ = {}\n",
    "        for i in range(1900,2001):\n",
    "            dict_[i] = 0\n",
    "        for i,j in zip(birth,death):\n",
    "            for k in range(i,j+1):\n",
    "                dict_[k] +=1\n",
    "        max_value = max(dict_.values())\n",
    "        for i,j in zip(dict_.keys(),dict_.values()):\n",
    "            if j == max_value:\n",
    "                return i\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self,birth:List[int], death: List[int]) ->int:\n",
    "        d = {}\n",
    "        for i in range(len(birth)):\n",
    "            c = birth[i]\n",
    "            s = death[i]\n",
    "            while c<=s:\n",
    "                if c in d:\n",
    "                    d[c] = d[c] + 1\n",
    "                else:\n",
    "                    d[c] = 0\n",
    "                c = c + 1\n",
    "        ls = list(d.items())\n",
    "        ls.sort(key = lambda x:x[0],reverse = True)\n",
    "        max = 0\n",
    "        \n",
    "        for key in ls:\n",
    "            if key[1] >= max:\n",
    "                max = key[1]\n",
    "                imax = key\n",
    "            \n",
    "        return imax[0]\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def maxAliveYear(self,birth:List[int], death: List[int]) ->int:\n",
    "        #bir表示每一年出生的人数，dea表示每一年死亡的人数\n",
    "        bir = collections.Counter(birth)\n",
    "        dea = collections.Counter(death)\n",
    "        #v表示活着的人数，max表示最大存活的人数，y表示最大的存货年份\n",
    "        v , max , y = 0 , 0 , None\n",
    "        for i in range(1900,2001):\n",
    "            v = v + bir[i]\n",
    "            v = v - dea[i-1]\n",
    "            if (v > max):\n",
    "                max = v\n",
    "                y = i\n",
    "        return y\n",
    "'''\n",
    "'''\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        min_year = min(birth)\n",
    "        max_year = max(death)\n",
    "        birth = [b - min_year for b in birth]\n",
    "        death = [d - min_year for d in death]\n",
    "        amount = [0] * (max_year - min_year + 2)\n",
    "        for b in birth:\n",
    "            amount[b] += 1\n",
    "        for d in death:\n",
    "            amount[d+1] -= 1\n",
    "        target_i, target_sum = 0, amount[0]\n",
    "        for i in range(1, len(amount)):\n",
    "            amount[i] += amount[i-1]\n",
    "            if amount[i] > target_sum:\n",
    "                target_sum = amount[i]\n",
    "                target_i = i\n",
    "        return target_i + min_year\n",
    "'''\n",
    "'''\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        years = [0] * 102 # Create a list of 102 years (from 1900 to 2001)\n",
    "        \n",
    "        for i in range(len(birth)):\n",
    "            birth_year = birth[i] - 1900\n",
    "            death_year = death[i] - 1900\n",
    "            years[birth_year] += 1\n",
    "            if death_year + 1 < 102:\n",
    "                years[death_year + 1] -= 1\n",
    "        \n",
    "        max_alive = years[0]\n",
    "        max_alive_year = 1900\n",
    "        current_alive = max_alive\n",
    "        \n",
    "        for year in range(1, 102):\n",
    "            current_alive += years[year]\n",
    "            if current_alive > max_alive:\n",
    "                max_alive = current_alive\n",
    "                max_alive_year = 1900 + year\n",
    "                \n",
    "        return max_alive_year\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        birth.sort()\n",
    "        death.sort()\n",
    "        total = 0\n",
    "        ans = 0\n",
    "        l1, l2, r1, r2 = 0, -1, len(birth), len(death)\n",
    "        for l1 in range(r1):\n",
    "            while l2 + 1 < r2 and death[l2 + 1] < birth[l1]:\n",
    "                l2 += 1\n",
    "            if total < l1 - l2:\n",
    "                total = l1 - l2\n",
    "                ans = birth[l1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        b = collections.Counter(birth)\n",
    "        d = collections.Counter(death)\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        year = 0\n",
    "        for i in range(1900, 2001):\n",
    "            tmp += b[i]\n",
    "            tmp -= d[i-1]\n",
    "            if tmp > res:\n",
    "                res = tmp\n",
    "                year = i\n",
    "\n",
    "        return year\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res = collections.defaultdict(int)\n",
    "        for i in range(len(birth)):\n",
    "            for year in range(birth[i], death[i] + 1):\n",
    "                res[year] += 1\n",
    "        res = sorted(res.items(), key=lambda x: (x[1], -x[0]), reverse=True)\n",
    "        return res[0][0]            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        alive = [0] * 102\n",
    "        for b in birth:\n",
    "            alive[b - 1900] += 1\n",
    "        for d in death:\n",
    "            alive[d - 1899] -= 1\n",
    "        res = list(accumulate(alive))\n",
    "        return res.index(max(res)) + 1900\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        b = collections.Counter(birth)\n",
    "        d = collections.Counter(death)\n",
    "        sv, maxsv, yr = 0, 0, None\n",
    "        for i in range(1900, 2001):\n",
    "            sv += b[i]\n",
    "            sv -= d[i-1]\n",
    "            if sv > maxsv:\n",
    "                maxsv, yr = sv, i\n",
    "        return yr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        diff = [0] * 102\n",
    "        for b, d in zip(birth, death):\n",
    "            diff[b - 1900] += 1\n",
    "            diff[d - 1900 + 1] -= 1\n",
    "        ans = mx = 0\n",
    "        for i, x in enumerate(accumulate(diff)):\n",
    "            if x > mx:\n",
    "                ans = i \n",
    "                mx = x \n",
    "        return ans + 1900 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        birth.sort()\n",
    "        death.sort()\n",
    "        j = 0\n",
    "        res = 0\n",
    "        mx = 0\n",
    "        ans = 0\n",
    "        for i in range(len(birth)):\n",
    "            if not i:\n",
    "                res += 1\n",
    "                mx += 1\n",
    "                ans = birth[i]\n",
    "                continue\n",
    "            res += 1\n",
    "            while death[j] < birth[i]:\n",
    "                j += 1\n",
    "                res -= 1\n",
    "            if res > mx:\n",
    "                mx = res\n",
    "                ans = birth[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(birth)\n",
    "        incdec = [0] * 102\n",
    "        \n",
    "        for i in range(n):\n",
    "            incdec[birth[i] - 1900] += 1\n",
    "            incdec[death[i] - 1900 + 1] -= 1\n",
    "\n",
    "        del incdec[101]\n",
    "        for i in range(1, 101):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        max_value = max(incdec)\n",
    "\n",
    "        for i in range(101):\n",
    "            if incdec[i] == max_value:\n",
    "                return i + 1900\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        a=[0]*2002\n",
    "        n=len(birth)\n",
    "        for i in range(n):\n",
    "            a[birth[i]]+=1\n",
    "            a[death[i]+1]-=1\n",
    "            \n",
    "        res=0\n",
    "        count=0\n",
    "        s=0\n",
    "        for i in range(1900,2001):\n",
    "            s+=a[i]\n",
    "            if s>count:\n",
    "                count=s\n",
    "                res=i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        # 差分数组\n",
    "        acc = collections.defaultdict(int)\n",
    "        n = len(birth)\n",
    "        for i in range(n):\n",
    "            acc[birth[i]]+=1\n",
    "            acc[death[i]+1]-=1\n",
    "        res,mx,total = 0,0,0\n",
    "        val = list(acc.keys())\n",
    "        val.sort()\n",
    "        for c in val:\n",
    "            total+=acc[c]\n",
    "            if mx<total:\n",
    "                mx = total\n",
    "                res = c\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        A=[0]*(102)\n",
    "        for a,b in zip(birth,death):\n",
    "            A[a-1900]+=1\n",
    "            A[b-1900+1]-=1\n",
    "        ma=-1\n",
    "        ans=0\n",
    "        for i in range(1,101):\n",
    "            A[i]+=A[i-1]\n",
    "            if A[i]>ma:\n",
    "                ma=A[i]\n",
    "                ans=i+1900\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        start_year = min(birth)\n",
    "        end_year = max(death)\n",
    "        years_range = end_year - start_year + 1\n",
    "\n",
    "        table = [0] * years_range\n",
    "\n",
    "        for i in range(len(birth)):\n",
    "            for j in range(birth[i], death[i] + 1):\n",
    "                table[j - start_year] += 1\n",
    "\n",
    "        max_alive_count = 0\n",
    "        max_alive_year = start_year\n",
    "\n",
    "        for year in range(years_range):\n",
    "            if table[year] > max_alive_count:\n",
    "                max_alive_count = table[year]\n",
    "                max_alive_year = year + start_year\n",
    "\n",
    "        return max_alive_year\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        b = collections.Counter(birth)\n",
    "        d = collections.Counter(death)\n",
    "        v,maxv,y = 0,0,None\n",
    "        for i in range(1900,2001):\n",
    "            v += b[i]\n",
    "            v -= d[i-1]\n",
    "            if v>maxv: maxv,y=v,i\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        # 使用哈希记录年份的差分值\n",
    "        diff = defaultdict(int)\n",
    "        n = len(birth)\n",
    "        for i in range(n):\n",
    "            diff[birth[i]] += 1\n",
    "            diff[death[i]+1] -= 1\n",
    "        # 按照年份进行排序\n",
    "        years = list(diff.keys())\n",
    "        years.sort()\n",
    "        # 从小到大遍历年份进行累加并更新最后结果\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        pre = 0\n",
    "        for year in years:\n",
    "            pre += diff[year]\n",
    "            if pre > count:\n",
    "                count = pre\n",
    "                ans = year\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res = 0\n",
    "        l = []\n",
    "        i, j =0, 0\n",
    "        birth.sort()\n",
    "        death.sort()\n",
    "        while i < len(birth):\n",
    "            if birth[i] <= death[j]:\n",
    "                res += 1\n",
    "                l.append(res)\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                res -= 1\n",
    "        n = l.index(max(l))\n",
    "        return birth[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res = []\n",
    "        len_bd = len(birth)\n",
    "        birth_start = min(birth)\n",
    "        death_end = max(death)\n",
    "        if len_bd == 0:\n",
    "            return res\n",
    "        if birth[-1] == death[-1]:\n",
    "            res = len_bd\n",
    "            return res\n",
    "        for i in range(birth_start, death_end+1):\n",
    "            count_year = 0\n",
    "            for j in range(len_bd):\n",
    "                if birth[j] <= i <= death[j]:\n",
    "                    count_year += 1\n",
    "            res.append(count_year)\n",
    "\n",
    "        ress = max(res)\n",
    "        for k in range(len(res)):\n",
    "            if res[k] == ress:\n",
    "                return birth_start + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        # 使用哈希记录年份的差分值\n",
    "        diff = defaultdict(int)\n",
    "        n = len(birth)\n",
    "        for i in range(n):\n",
    "            diff[birth[i]] += 1\n",
    "            diff[death[i]+1] -= 1\n",
    "        # 按照年份进行排序\n",
    "        years = list(diff.keys())\n",
    "        years.sort()\n",
    "        # 从小到大遍历年份进行累加并更新最后结果\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        pre = 0\n",
    "        for year in years:\n",
    "            pre += diff[year]\n",
    "            if pre > count:\n",
    "                count = pre\n",
    "                ans = year\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        a=[0]*2001\n",
    "        n=len(birth)\n",
    "        for i in range(n):\n",
    "            for j in range(birth[i], death[i]+1):\n",
    "                a[j]+=1\n",
    "        res=0\n",
    "        count=0\n",
    "        for i in range(1900,2001):\n",
    "            if a[i]>count:\n",
    "                res=i\n",
    "                count=a[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        #统计出生每一年出生与死亡的人数\n",
    "        b = collections.Counter(birth)\n",
    "        d = collections.Counter(death)\n",
    "        #初始化活着的人数v、最大存活数maxv、最大存活数对应年份\n",
    "        v,maxv,y = 0,0,None\n",
    "        #迭代所有年份\n",
    "        for i in range(1900,2001):\n",
    "            #存活的人数= v+今年出生人数-去年死亡人数\n",
    "            v += b[i]\n",
    "            v -= d[i-1]\n",
    "            #判断是否为最大存活人数年\n",
    "            if v>maxv: maxv,y=v,i\n",
    "        return y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        # 差分数组\n",
    "        acc = collections.defaultdict(int)\n",
    "        n = len(birth)\n",
    "        for i in range(n):\n",
    "            acc[birth[i]]+=1\n",
    "            acc[death[i]+1]-=1\n",
    "        res,mx,total = 0,0,0\n",
    "        for i in range(1900,2001):\n",
    "            total+=acc[i]\n",
    "            if mx<total:\n",
    "                mx = total\n",
    "                res = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res, n = 0, len(birth)\n",
    "        count = [0] * 102\n",
    "        for idx in range(n):\n",
    "            count[birth[idx]-1900] += 1\n",
    "            count[death[idx]+1-1900] -= 1\n",
    "         # 前缀和，表示当前年份存活的数量\n",
    "        forwardSum, lastPeo = 0, 0\n",
    "        for idx, peo in enumerate(count):\n",
    "            forwardSum += peo\n",
    "            if forwardSum > lastPeo:\n",
    "                lastPeo = forwardSum\n",
    "                res = idx + 1900\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        # 使用哈希记录年份的差分值\n",
    "        diff = defaultdict(int)\n",
    "        n = len(birth)\n",
    "        for i in range(n):\n",
    "            diff[birth[i]] += 1\n",
    "            diff[death[i]+1] -= 1\n",
    "        # 按照年份进行排序\n",
    "        years = list(diff.keys())\n",
    "        years.sort()\n",
    "        # 从小到大遍历年份进行累加并更新最后结果\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        pre = 0\n",
    "        for year in years:\n",
    "            pre += diff[year]\n",
    "            if pre > count:\n",
    "                count = pre\n",
    "                ans = year\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res = []\n",
    "        len_bd = len(birth)\n",
    "        birth_start = min(birth)\n",
    "        death_end = max(death)\n",
    "        if len_bd == 0:\n",
    "            return res\n",
    "        if birth[-1] == death[-1]:\n",
    "            res = len_bd\n",
    "            return res\n",
    "        for i in range(birth_start, death_end+1):\n",
    "            count_year = 0\n",
    "            for j in range(len_bd):\n",
    "                if birth[j] <= i <= death[j]:\n",
    "                    count_year += 1\n",
    "            res.append(count_year)\n",
    "\n",
    "        ress = max(res)\n",
    "        for k in range(len(res)):\n",
    "            if res[k] == ress:\n",
    "                return birth_start + k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        birth.sort()\n",
    "        death.sort()\n",
    "        print(birth)\n",
    "        print(death)\n",
    "        numOfPerson = len(birth)\n",
    "        min_year = birth[0]\n",
    "        max_year = death[numOfPerson - 1]\n",
    "        ans_num = 0\n",
    "        ans_year = 0\n",
    "        current_num = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        for current_year in range(min_year, max_year + 2):\n",
    "            while i <= numOfPerson - 1 and current_year == birth[i]:\n",
    "                i += 1\n",
    "                current_num += 1\n",
    "            while j <= numOfPerson - 1 and current_year == death[j] + 1:\n",
    "                j += 1\n",
    "                current_num -= 1\n",
    "            if current_num > ans_num:\n",
    "                ans_num = current_num\n",
    "                ans_year = current_year\n",
    "            print(i,\" \",j)\n",
    "        return ans_year\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def maxAliveYear(self,birth:List[int], death: List[int]) ->int:\n",
    "        d = {}\n",
    "        for i in range(len(birth)):\n",
    "            c = birth[i]\n",
    "            s = death[i]\n",
    "            while c<=s:\n",
    "                if c in d:\n",
    "                    d[c] = d[c] + 1\n",
    "                else:\n",
    "                    d[c] = 0\n",
    "                c = c + 1\n",
    "        ls = list(d.items())\n",
    "        ls.sort(key = lambda x:x[1] , reverse = True )\n",
    "        fls = ls[0]\n",
    "        return fls[0]\n",
    "'''\n",
    "'''\n",
    "class Solution:\n",
    "    def maxAliveYear(self,birth:List[int], death: List[int]) ->int:\n",
    "        #bir表示每一年出生的人数，dea表示每一年死亡的人数\n",
    "        bir = collections.Counter(birth)\n",
    "        dea = collections.Counter(death)\n",
    "        #v表示活着的人数，max表示最大存活的人数，y表示最大的存货年份\n",
    "        v , max , y = 0 , 0 , None\n",
    "        for i in range(1900,2001):\n",
    "            v = v + bir[i]\n",
    "            v = v - dea[i-1]\n",
    "            if (v > max):\n",
    "                max = v\n",
    "                y = i\n",
    "        return y\n",
    "'''\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        min_year = min(birth)\n",
    "        max_year = max(death)\n",
    "        birth = [b - min_year for b in birth]\n",
    "        death = [d - min_year for d in death]\n",
    "        amount = [0] * (max_year - min_year + 2)\n",
    "        for b in birth:\n",
    "            amount[b] += 1\n",
    "        for d in death:\n",
    "            amount[d+1] -= 1\n",
    "        target_i, target_sum = 0, amount[0]\n",
    "        for i in range(1, len(amount)):\n",
    "            amount[i] += amount[i-1]\n",
    "            if amount[i] > target_sum:\n",
    "                target_sum = amount[i]\n",
    "                target_i = i\n",
    "        return target_i + min_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "\n",
    "        birth_map = {}\n",
    "        death_map = {}\n",
    "\n",
    "        for bir, dead in zip(birth, death):\n",
    "\n",
    "            if bir not in birth_map:\n",
    "                birth_map[bir] = []\n",
    "            birth_map[bir].append(dead)\n",
    "\n",
    "            if dead not in death_map:\n",
    "                death_map[dead] = []\n",
    "            death_map[dead].append(bir)\n",
    "\n",
    "        # Solution: Dynamic programming\n",
    "        \n",
    "        # Step 1: Construct the state-transition matrix\n",
    "        dp = [0] * 101\n",
    "\n",
    "        # Step 2: Construct the starting point\n",
    "        dp[0] = 0 if 1900 not in birth_map else len(birth_map[1900])\n",
    "\n",
    "        # Step 3: Define the relationship\n",
    "        for i in range(1, 101):\n",
    "            dp[i] = dp[i - 1]\n",
    "            \n",
    "            if i + 1900 in birth_map:\n",
    "                dp[i] += len(birth_map[i + 1900])\n",
    "            \n",
    "            if i + 1899 in death_map:\n",
    "                dp[i] -= sum([bir < i + 1900 for bir in death_map[i + 1899]])\n",
    "        \n",
    "        return dp.index(max(dp)) + 1900"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        data = [0 for i in range(10001)] \n",
    "        for i,j in zip(birth, death): \n",
    "            while i <= j : \n",
    "                data[i] += 1\n",
    "                i += 1\n",
    "        minyear = 0\n",
    "        minnow = 0\n",
    "        for idx,val in enumerate(data) : \n",
    "            if val > minnow : \n",
    "                minnow = val\n",
    "                minyear = idx\n",
    "        return minyear"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "\n",
    "        # 差分数组\n",
    "        # https://baijiahao.baidu.com/s?id=1726813595390831261&wfr=spider&for=pc\n",
    "\n",
    "        n = len(birth)\n",
    "\n",
    "        # 计算差分数组（原数组a可以看做全部值为0，根据差分数组计算法，得差分数组diff[i]=a[i]-a[i-1]，所以差分数组全部元素值也是0）\n",
    "        diff = [0 for _ in range(2002)] # 可以取值到2001，因为元素值最大是2000\n",
    "        for i in range(n):\n",
    "            start, end = birth[i], death[i]\n",
    "            \n",
    "            # 本来是需要在时间轴数组上把start~end间的所有点都加1，但是用了差分数组，只需要操作首尾两个点即可\n",
    "            diff[start] += 1\n",
    "            diff[end+1] -= 1\n",
    "        \n",
    "        # 问题可以看成问数轴1900到2000得范围内哪个点被覆盖得次数最多\n",
    "        # 假设上面说的数轴数组是a，则根据差分数组计算法：a[i] = a[i-1] + diff[i]，即： a_i += diff[i]\n",
    "        a_i = 0 # 年份数轴数组（差分数组的原数组）的每一个值\n",
    "        idx = -1 # 记录最大值位置\n",
    "        max_v = float(\"-inf\") # 记录最大值\n",
    "\n",
    "        for i in range(1900, 2001):\n",
    "            a_i += diff[i] # 通过查分数组计算原数组\n",
    "\n",
    "            if a_i > max_v:\n",
    "                max_v = a_i\n",
    "                idx = i\n",
    "\n",
    "        return idx     \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        years = sorted([(b, -1) for b in birth] + [(d, 1) for d in death])\n",
    "        cnt, ans, year = 0, 0, 0\n",
    "        for y, f in years:\n",
    "            cnt -= f\n",
    "            if cnt > ans:\n",
    "                year = y\n",
    "                ans = cnt\n",
    "        return year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res = [0 for _ in range(2003)]\n",
    "        for i in range(len(birth)):\n",
    "            res[birth[i]] += 1\n",
    "            res[death[i] + 1] -= 1\n",
    "        mx = 0\n",
    "        re = 1900\n",
    "        tmp = 0\n",
    "        for i in range(1900, 2000+1):\n",
    "            tmp += res[i]\n",
    "            if tmp > mx:\n",
    "                tmp = mx\n",
    "                re = i\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "     event=[]\n",
    "     for   x in death :\n",
    "       event.append([x+1,-1])\n",
    "     for   x in birth :\n",
    "       event.append([x,1])\n",
    "     event.sort(key=lambda x:x[0])\n",
    "     max=0\n",
    "     survival=0\n",
    "     ans=0\n",
    "     for   x in event :\n",
    "       survival+=x[1]\n",
    "       if   survival>max :\n",
    "           max=survival\n",
    "           ans=x[0]\n",
    "     return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        seq = [(i, 1) for i in birth] + [(j, 0) for j in death]\n",
    "        seq.sort(key = lambda x:x[0]-0.1*x[1]) # value+sign*0.1, make sure positive value before\n",
    "        yr = seq[0][0]\n",
    "        Max = 1\n",
    "        cur = seq[0][0] # current population, seq[0][1] must be 1\n",
    "        for i in range(1, len(seq)):\n",
    "            sign = seq[i][1]\n",
    "            if sign: # sign==1\n",
    "               cur += 1\n",
    "               if cur > Max:\n",
    "                   Max = cur\n",
    "                   yr = seq[i][0]\n",
    "            else: # sign==0\n",
    "                cur -= 1\n",
    "        return yr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        prev_year = -1\n",
    "        prev_death = 0\n",
    "\n",
    "        array_to_sort = []\n",
    "\n",
    "        for b in birth:\n",
    "            array_to_sort.append((b, 0))\n",
    "        for d in death:\n",
    "            array_to_sort.append((d, 1))\n",
    "        \n",
    "        array_to_sort = sorted(array_to_sort)\n",
    "\n",
    "        print (array_to_sort)\n",
    "\n",
    "        num_people = 0\n",
    "        max_people = 0\n",
    "        max_year = 0\n",
    "        for year_death in array_to_sort:\n",
    "            year, death = year_death\n",
    "            if year != prev_year:\n",
    "                num_people -= prev_death\n",
    "                prev_year = year\n",
    "                prev_death = 0\n",
    "            if death:\n",
    "                prev_death += 1\n",
    "            else:\n",
    "                num_people += 1\n",
    "\n",
    "            print (year, death, num_people)\n",
    "\n",
    "            if num_people > max_people:\n",
    "                max_people = max(max_people, num_people)\n",
    "                max_year = year\n",
    "        \n",
    "        return max_year\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        res={}\n",
    "        bd_list=[]\n",
    "        for i in range(len(birth)):\n",
    "            bd_list.append((birth[i],death[i]))\n",
    "        cont=0 \n",
    "        for i in range(1900,2001):\n",
    "            cont+=birth.count(i)\n",
    "            if cont not in res:\n",
    "                res[cont]=[i]\n",
    "            else:\n",
    "                res[cont].append(i)\n",
    "            cont-=death.count(i)\n",
    "        res_sorted=sorted(res.items(),key=lambda a:a[0])[::-1]\n",
    "        return res_sorted[0][1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(death)\n",
    "        temp = sorted(list(zip(birth, [1]*n)) + list(zip([d+1 for d in death], [-1]*n)), key=lambda x: x[0])\n",
    "        age_map = {}\n",
    "        num = 0\n",
    "        for t in temp:\n",
    "            num += t[1]\n",
    "            age_map[t[0]] = num\n",
    "        ret = (0, 0)\n",
    "        for k, v in age_map.items():\n",
    "            if v > ret[1]:\n",
    "                ret = k, v\n",
    "        return ret[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        ans, mx = -inf, -inf\n",
    "        sl = SortedList()\n",
    "        g = defaultdict(list)\n",
    "        for x, y in zip(birth, death):\n",
    "            g[x].append(y)\n",
    "        for x in range(1900, 2001):\n",
    "            for y in g[x]: sl.add(y)\n",
    "            while sl and sl[0] < x: sl.pop(0)\n",
    "            if len(sl) > mx:\n",
    "                mx = len(sl)\n",
    "                ans = x\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int: \n",
    "        heap = []\n",
    "        cnt = maxn = b = 0\n",
    "        ans = 0\n",
    "        n = len(birth)\n",
    "        inf = [(birth[i], death[i]) for i in range(n)]\n",
    "        inf.sort()\n",
    "        for i in range(n):\n",
    "            if not heap:\n",
    "                b = inf[i][0]\n",
    "                heapq.heappush(heap, inf[i][1])\n",
    "                cnt = 1\n",
    "                if cnt > maxn:\n",
    "                    maxn = cnt\n",
    "                    ans = b\n",
    "            else:\n",
    "                b = inf[i][0]\n",
    "                while heap and heap[0] < b:\n",
    "                    heapq.heappop(heap)\n",
    "                    cnt -= 1\n",
    "                heapq.heappush(heap, inf[i][1])\n",
    "                cnt += 1\n",
    "                if cnt > maxn:\n",
    "                    maxn = cnt\n",
    "                    ans = b\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        if not birth:\n",
    "            return 0\n",
    "\n",
    "        if len(birth) == 1:\n",
    "            return birth[0]\n",
    "\n",
    "        birth_death = [(bi, di) for bi, di in zip(birth, death)]\n",
    "        birth_death = sorted(birth_death, key=lambda x: x[0])\n",
    "        max_num, max_year = 1, birth_death[0][0]\n",
    "        death_queue = [birth_death[0][1]]\n",
    "        num = 1\n",
    "        for bi, di in birth_death[1:]:\n",
    "            while death_queue and death_queue[0] < bi:\n",
    "                death_queue.pop(0)\n",
    "                num -= 1\n",
    "\n",
    "            if not death_queue:\n",
    "                death_queue.append(di)\n",
    "                continue\n",
    "\n",
    "            ind = num - 1\n",
    "            while ind >= 0 and di < death_queue[ind]:\n",
    "                ind -= 1\n",
    "            death_queue = death_queue[:ind+1] + [di] + death_queue[ind+1:]\n",
    "\n",
    "            num += 1\n",
    "            if num > max_num:\n",
    "                max_num = num\n",
    "                max_year = bi\n",
    "\n",
    "        return max_year\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(birth)\n",
    "        arr = []\n",
    "        for i in range(n):\n",
    "            arr.append([birth[i],1])\n",
    "            arr.append([death[i]+1,-1])        \n",
    "        arr.sort(key=lambda x : x[0])\n",
    "        ans = arr[0][0]\n",
    "        maxnum = 0 \n",
    "        res = 0\n",
    "        for i in range(2*n):\n",
    "            res += arr[i][1]\n",
    "            if i+1 != 2*n and arr[i][0] == arr[i+1][0]:\n",
    "                continue\n",
    "            if res > maxnum:\n",
    "                maxnum = res \n",
    "                ans = arr[i][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        # 有人刚出生的那天肯定是人数最多的，也符合题意\n",
    "        # 生成一个人物列表\n",
    "        for i in range(len(birth)):\n",
    "            birth[i] = (birth[i], 1)\n",
    "            death[i] = (death[i], -1)\n",
    "        all_list = birth + death\n",
    "        # 进行排序，由于死亡当年不计入人数，那么就需要：先计算死亡，后出生，这样最大值就会保证\n",
    "        all_list.sort(key=lambda x: (x[0], -x[1]))\n",
    "        max_person = 0\n",
    "        count_person = 0\n",
    "        for i in range(len(all_list)):\n",
    "            count_person = all_list[i][1] + count_person\n",
    "            if count_person > max_person:\n",
    "                date = all_list[i][0]\n",
    "            max_person = max(max_person, count_person)\n",
    "        return date"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        if not birth:\n",
    "            return 0\n",
    "\n",
    "        birth_death = [(bi, di) for bi, di in zip(birth, death)]\n",
    "        birth_death = sorted(birth_death, key=lambda x: x[0])\n",
    "        max_num, max_year = 1, birth_death[0][0]\n",
    "        death_queue = [birth_death[0][1]]\n",
    "        num = 1\n",
    "\n",
    "        for bi, di in birth_death[1:]:\n",
    "            while death_queue and death_queue[0] < bi:\n",
    "                death_queue.pop(0)\n",
    "                num -= 1\n",
    "\n",
    "            if not death_queue:\n",
    "                death_queue.append(di)\n",
    "                continue\n",
    "\n",
    "            ind = num - 1\n",
    "            while ind >= 0 and di < death_queue[ind]:\n",
    "                ind -= 1\n",
    "            death_queue = death_queue[:ind+1] + [di] + death_queue[ind+1:]\n",
    "\n",
    "            num += 1\n",
    "            if num > max_num:\n",
    "                max_num = num\n",
    "                max_year = bi\n",
    "\n",
    "        return max_year\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "\n",
    "        for d in death:\n",
    "            birth.append(-d)\n",
    "        \n",
    "        birth = sorted(birth, key=lambda x:(abs(x),-x))\n",
    "\n",
    "        max_num = 0\n",
    "        max_year = None\n",
    "        living_num = 0\n",
    "        for year in birth:\n",
    "            if year > 0:\n",
    "                living_num += 1\n",
    "                if living_num > max_num:\n",
    "                    max_num = living_num\n",
    "                    max_year = year\n",
    "            else:\n",
    "                living_num -= 1\n",
    "\n",
    "        return max_year\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        men = []\n",
    "        for i,byear in enumerate(birth):\n",
    "            men.append([byear,0])\n",
    "        for j,dyear in enumerate(death):\n",
    "            men.append([dyear,1])\n",
    "        men = sorted(men)\n",
    "        x = [0]*len(men)\n",
    "        m=0\n",
    "        j =0\n",
    "        for i,life in enumerate(men):\n",
    "            if life[1]==0:\n",
    "                if  i>0:\n",
    "                    x[i]=x[i-1]+1 \n",
    "                else:\n",
    "                    x[i]=1\n",
    "            else :\n",
    "                if i>0:\n",
    "                    x[i]=x[i-1]-1\n",
    "                else:\n",
    "                    x[i]=-1\n",
    "            j = i if x[i]>m else j\n",
    "            m = max(x[i],m)\n",
    "        return men[j][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(birth)\n",
    "        records = list()\n",
    "        for i in range(n):\n",
    "            records.append((birth[i], death[i]))\n",
    "        records = sorted(records)\n",
    "\n",
    "        ans = 0\n",
    "        max_num = 0\n",
    "        tmp = list()\n",
    "        heapq.heapify(tmp)\n",
    "        for record in records:\n",
    "            cur_year = record[0]\n",
    "            while len(tmp) > 0:\n",
    "                if tmp[0][0] < cur_year:\n",
    "                    heapq.heappop(tmp)\n",
    "                else:\n",
    "                    break\n",
    "            heapq.heappush(tmp, (record[1], record[0]))\n",
    "            if len(tmp) > max_num:\n",
    "                max_num = len(tmp)\n",
    "                ans = cur_year\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        people = [(d, b) for d, b in zip(death, birth)]\n",
    "        people.sort(key=lambda x: x[1])\n",
    "        people = deque(people)\n",
    "        \n",
    "        max_num, res = -1, -1\n",
    "        q = []\n",
    "        for i in range(1900, 2000):\n",
    "            while people and people[0][1] <= i:\n",
    "                heapq.heappush(q, people[0])\n",
    "                people.popleft()\n",
    "            \n",
    "            while q and q[0][0] < i:\n",
    "                heapq.heappop(q)\n",
    "            \n",
    "            if len(q) > max_num:\n",
    "                max_num = len(q)\n",
    "                res = i\n",
    "\n",
    "            if len(people) == 0:\n",
    "                break\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        x = list(map(list,zip(*[birth,death])))\n",
    "        y1 = min([b for a in x for b in a])\n",
    "        y2 = max([b for a in x for b in a])\n",
    "        years = list(range(y1,y2+1))\n",
    "        score1 = []\n",
    "        for y in years:\n",
    "            #print(y)\n",
    "            score = 0\n",
    "            j = 0\n",
    "            while j <len(x):\n",
    "                #print(x[j])\n",
    "                if y <=max(x[j]) and y>=min(x[j]):\n",
    "                    score = score + 1\n",
    "                j += 1\n",
    "                #print(score)\n",
    "            score1.append(score)\n",
    "            #print('----------------')\n",
    "            \n",
    "        #print(years)\n",
    "        #print(score1)\n",
    "        return (years[score1.index(max(score1))])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        people = [(d, b) for d, b in zip(death, birth)]\n",
    "        people.sort(key=lambda x: x[1])\n",
    "\n",
    "        res = []\n",
    "        q = []\n",
    "        for i in range(1900, 2000):\n",
    "            while people and people[0][1] <= i:\n",
    "                heapq.heappush(q, people[0])\n",
    "                people = people[1:]\n",
    "            \n",
    "            \n",
    "            while q and q[0][0] < i:\n",
    "                heapq.heappop(q)\n",
    "            \n",
    "            res.append(len(q))\n",
    "\n",
    "            if len(people) == 0:\n",
    "                break\n",
    "        print(res, len(res))\n",
    "        return 1900 + res.index(max(res))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        people = [(d, b) for d, b in zip(death, birth)]\n",
    "        people.sort(key=lambda x: x[1])\n",
    "        people = deque(people)\n",
    "        res = []\n",
    "        q = []\n",
    "        for i in range(1900, 2000):\n",
    "            while people and people[0][1] <= i:\n",
    "                heapq.heappush(q, people[0])\n",
    "                people.popleft()\n",
    "            \n",
    "            while q and q[0][0] < i:\n",
    "                heapq.heappop(q)\n",
    "            \n",
    "            res.append(len(q))\n",
    "\n",
    "            if len(people) == 0:\n",
    "                break\n",
    "        print(res, len(res))\n",
    "        return 1900 + res.index(max(res))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(birth)\n",
    "        pairs = []\n",
    "        for i in range(n):\n",
    "            pairs.append([birth[i], death[i]])\n",
    "        pairs.sort()\n",
    "        heap = []\n",
    "        ans = 0\n",
    "        ans_year = 0\n",
    "        for pair in pairs:\n",
    "            while len(heap) > 0 and heap[0][0] < pair[0]:\n",
    "                heapq.heappop(heap)\n",
    "            heapq.heappush(heap, [pair[1], pair[0]])\n",
    "            if len(heap) > ans:\n",
    "                ans_year = pair[0]\n",
    "                ans = len(heap)\n",
    "\n",
    "        return ans_year\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        if not birth:\n",
    "            return 0\n",
    "            \n",
    "        if len(birth) == 1:\n",
    "            return birth[0]\n",
    "\n",
    "        birth_death = [(bi, di) for bi, di in zip(birth, death)]\n",
    "        birth_death = sorted(birth_death, key=lambda x: x[0])\n",
    "        print(birth_death)\n",
    "        max_num, max_year = 1, birth_death[0][0]\n",
    "        death_queue = [birth_death[0][1]]\n",
    "        num = 1\n",
    "        for bi, di in birth_death[1:]:\n",
    "            while death_queue and death_queue[0] < bi:\n",
    "                death_queue.pop(0)\n",
    "                num -= 1\n",
    "\n",
    "            if not death_queue:\n",
    "                death_queue.append(di)\n",
    "                continue\n",
    "\n",
    "            ind = num - 1\n",
    "            while ind >= 0 and di < death_queue[ind]:\n",
    "                ind -= 1\n",
    "            death_queue = death_queue[:ind+1] + [di] + death_queue[ind+1:]\n",
    "            num += 1\n",
    "            if num > max_num:\n",
    "                max_num = num\n",
    "                max_year = bi\n",
    "\n",
    "        return max_year\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(birth)\n",
    "        save = [[birth[i],death[i]] for i in range(n)]\n",
    "        save.sort(key = lambda k:k[0], reverse = True)\n",
    "        res = save[-1][0]\n",
    "        qwq = 0\n",
    "        alive = []\n",
    "        heapq.heapify(alive)\n",
    "        while len(save) != 0:\n",
    "            eee = save.pop()\n",
    "            heapq.heappush(alive, eee[1])\n",
    "            while alive != None and alive[0] < eee[0]:\n",
    "                heapq.heappop(alive)\n",
    "            if len(alive) > qwq:\n",
    "                qwq = len(alive)\n",
    "                res = eee[0]\n",
    "        return res            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        ref = []\n",
    "        for b in birth:\n",
    "            ref.append((b, 1))\n",
    "        for d in death:\n",
    "            ref.append((d, -1))\n",
    "        ans = 0\n",
    "        count, reach = 0, 0\n",
    "        ref.sort(key = lambda x:(x[0], -x[1]))\n",
    "        for x, val in ref:\n",
    "            count += val\n",
    "            if count > reach:\n",
    "                reach = count\n",
    "                ans = x\n",
    "        return(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        if len(birth) == 0:\n",
    "            return -1\n",
    "        y_heap = []\n",
    "        for year in birth:\n",
    "            heapq.heappush(y_heap,(year, +1))\n",
    "        for year in death:\n",
    "            heapq.heappush(y_heap,(year+1, -1))\n",
    "\n",
    "        max_val = 0\n",
    "        max_val_y = 1900\n",
    "        cur_y = 1900\n",
    "        cur_p = 0\n",
    "        while len(y_heap) > 0:\n",
    "            (top_y, i) =   y_heap[0]\n",
    "            if top_y == cur_y:\n",
    "                cur_p += i\n",
    "                if cur_p > max_val:\n",
    "                    max_val = cur_p\n",
    "                    max_val_y = cur_y\n",
    "                heapq.heappop(y_heap)\n",
    "            else:\n",
    "                cur_y += 1\n",
    "        return max_val_y\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        time = []\n",
    "        for b in birth:\n",
    "            time.append((b, 0))\n",
    "        for d in death:\n",
    "            time.append((d, 1))\n",
    "        time = sorted(time, key=lambda x: (x[0], x[1]))\n",
    "        cur = 0\n",
    "        resNum, resIndex = 0, -1\n",
    "        for i in range(len(time)):\n",
    "            t, bd = time[i]\n",
    "            if bd == 0:\n",
    "                cur += 1\n",
    "                if cur > resNum:\n",
    "                    resNum = cur\n",
    "                    resIndex = t\n",
    "            else:\n",
    "                cur -= 1\n",
    "        return resIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        max_num = 0\n",
    "        max_year = 0\n",
    "        total = 0\n",
    "        actions = [(day, 1) for day in birth] + [(day, -1) for day in death]\n",
    "        actions.sort(key=lambda x: x[0])\n",
    "        for day, num in actions:\n",
    "            total += num\n",
    "            if total > max_num:\n",
    "                max_num = total\n",
    "                max_year = day\n",
    "        return max_year"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: List[int], death: List[int]) -> int:\n",
    "        n = len(birth)\n",
    "        save = [[birth[i],death[i]] for i in range(n)]\n",
    "        save.sort(key = lambda k:k[0], reverse = True)\n",
    "        res = save[-1][0]\n",
    "        qwq = 0\n",
    "        alive = []\n",
    "        heapq.heapify(alive)\n",
    "        while len(save) != 0:\n",
    "            eee = save.pop()\n",
    "            heapq.heappush(alive, eee[1])\n",
    "            while alive != None and alive[0] < eee[0]:\n",
    "                heapq.heappop(alive)\n",
    "            if len(alive) > qwq:\n",
    "                qwq = len(alive)\n",
    "                res = eee[0]\n",
    "        return res            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAliveYear(self, birth: list[int], death: list[int]) -> int:\n",
    "        dict = {}\n",
    "        l1,l2 = (list(t) for t in zip(*sorted(zip(birth, death))))\n",
    "        r,rc = l1[0],0\n",
    "        prev_birth,i = {},1\n",
    "        birth.sort()\n",
    "        prev_birth[birth[0]] = 0\n",
    "        death.append(birth[0])\n",
    "        while i < len(birth):\n",
    "            death.append(birth[i])\n",
    "            if birth[i] == birth[i-1]:\n",
    "                i += 1\n",
    "                continue\n",
    "            prev_birth[birth[i]] = i\n",
    "            i+=1\n",
    "        death.sort()  \n",
    "        prev_death, i = {}, 1\n",
    "        prev_death[death[0]] = 0\n",
    "        while i < len(death):\n",
    "            if death[i] == death[i-1]:\n",
    "                i+=1\n",
    "                continue\n",
    "            prev_death[death[i]] = i-prev_birth.get(death[i],0)\n",
    "            i+=1\n",
    "        dict[l1[0]] = 1\n",
    "        i =1\n",
    "        while i < len(l1):\n",
    "            if l1[i] == l1[i-1]:\n",
    "                dict[l1[i]] = dict[l1[i]] + 1\n",
    "                i += 1\n",
    "            else:\n",
    "                dict[l1[i]] = i - prev_death[l1[i]] +1\n",
    "                i += 1\n",
    "        for i in range(len(l1)):\n",
    "            if dict[l1[i]] > rc:\n",
    "                rc = dict[l1[i]]\n",
    "                r = l1[i]\n",
    "        return r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
